1204E - Natasha Sasha and the Prefix Sums - CodeForces Solution

#include <bits/stdc++.h>

using i64 = long long;



long long *fact, *inv;



template <class T>

T pow(T x, T n, T mod) {

    T ret = 1;

    while (n > 0) {

        if ((n & 1) == 1) ret = (ret * x) % mod;

        x = (x * x) % mod;

        n >>= 1;

    }

    return ret;

}



template <class T>

T inverse(T x, T p) { return pow(x, p - 2, p); }



void init_factorial(int n, long long mod) {

    fact = new long long[n + 1];

    inv = new long long[n + 1];

    fact[0] = 1;

    for (long long i = 1; i <= n; i++) fact[i] = fact[i - 1] * i % mod;

    inv[n] = inverse(fact[n], mod);

    for (long long i = n; i > 0; i--) inv[i - 1] = inv[i] * i % mod;

}



int main() {

    constexpr i64 mod = 998244853;

    int n, m;

    std::cin >> n >> m;

    int t = n + m;

    init_factorial(t, mod);



    i64 ret = n, all = fact[t] * inv[n] % mod * inv[m] % mod, s = all;

    for (int i = std::max(0, n - m); i < n; i++) {

        i64 q = fact[t] * inv[m + i + 1] % mod * inv[n - i - 1] % mod;

        ret = (ret + (s - q + mod) % mod * i % mod) % mod;

        s = q;

    }



    std::cout << ret << std::endl;



    return 0;

}